package com.liuke.study.leecode;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.lang.invoke.MutableCallSite;
import java.sql.SQLClientInfoException;

class Solution {

    /*
    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明：

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

    示例 1:

    输入: [2,2,1]
    输出: 1
    示例 2:

    输入: [4,1,2,1,2]
    输出: 4
    */
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (0 == i) {
                result = nums[i];
            } else {
                result = result ^ nums[i];
            }
        }

        return result;
    }

    /*
    给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

    如果所读的字符是字母，则将该字母写在磁带上。
    如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
    现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。


    示例 1：

    输入：S = "leet2code3", K = 10
    输出："o"
    解释：
    解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
    字符串中的第 10 个字母是 "o"。
    示例 2：

    输入：S = "ha22", K = 5
    输出："h"
    解释：
    解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
    示例 3：

    输入：S = "a2345678999999999999999", K = 1
    输出："a"
    解释：
    解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
    提示：

            2 <= S.length <= 100
    S 只包含小写字母与数字 2 到 9 。
    S 以字母开头。
            1 <= K <= 10^9
    解码后的字符串保证少于 2^63 个字母。*/
    public String decodeAtIndex(String S, int K) {
        // int ori = K;
        // if (0 == K) {
        //     return String.valueOf(S.charAt(K));
        // }
        // char[] chars = S.toCharArray();
        // StringBuilder result = new StringBuilder();
        // int index = 0;
        // for (char aChar : chars) {
        //
        //     if (aChar < '1' || aChar > '9') {
        //         result.append(aChar);
        //         index++;
        //         if (index == ori) {
        //             return String.valueOf(aChar);
        //         }
        //     } else {
        //         int anInt = Integer.parseInt(String.valueOf(aChar));
        //         String tmp = result.toString();
        //         for (int i = 1; i < anInt; i++) {
        //             result.append(tmp);
        //             if (index <= ori && ori <= index + tmp.length()) {
        //                 return String.valueOf(result.toString().charAt(K - 1));
        //             }
        //             index += tmp.length();
        //         }
        //         tmp = result.toString();
        //         K = K - (result.length() - tmp.length());
        //         result = new StringBuilder(tmp);
        //     }
        // }
        // return "";

        int n = S.length();
        // arr[i] 代表S.substring(0,i)解码后的长度
        long[] arr = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            char c = S.charAt(i - 1);
            if (Character.isDigit(c)) {   //如果是数字
                arr[i] = arr[i - 1] * Integer.valueOf(c + "");
            } else {
                arr[i] = arr[i - 1] + 1;
            }
            if (arr[i] >= K) {
                break;
            }
        }
        while (true) {
            int i = 1;
            while (arr[i] < K) {
                i++;
            }
            char c = S.charAt(i - 1);
            if (Character.isDigit(c)) {
                while (arr[i - 1] < K) {
                    K -= arr[i - 1];
                }
            } else {
                return c + "";
            }
        }

    }

	/*
	*给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

	你可以假设数组中无重复元素。

	示例 1:

	输入: [1,3,5,6], 5
	输出: 2
	示例 2:

	输入: [1,3,5,6], 2
	输出: 1
	示例 3:

	输入: [1,3,5,6], 7
	输出: 4
	示例 4:

	输入: [1,3,5,6], 0
	输出: 0
	*/

    public int searchInsert(int[] nums, int target) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return target <= nums[0] ? 0 : 1;
        }
        int begin = 0;
        int end = nums.length - 1;

        if (target < nums[0]) {
            return 0;
        }
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        while (begin <= end) {
            int index = (begin + end) / 2;
            if (end - begin == 1) {
                if (nums[begin] < target && nums[end] >= target) {
                    return begin + 1;
                } else if (target <= nums[begin]) {
                    return begin;
                }
            }
            if (nums[index] < target) {
                begin = index;
            } else {
                end = index;
            }
        }
        return -1;
    }

	/*
	实现 int sqrt(int x) 函数。

	计算并返回 x 的平方根，其中 x 是非负整数。

	由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

	示例 1:

	输入: 4
	输出: 2
	示例 2:

	输入: 8
	输出: 2
	说明: 8 的平方根是 2.82842...,
	     由于返回类型是整数，小数部分将被舍去。
	 */

    public int mySqrt(int x) {

        int begin = 1;
        int end = x / 2 + 1;
        if (x == 0) {
            return 0;
        }
        while (begin <= end) {
            int mid = (begin + end) >>> 1;
            if (end - begin == 1) {
                if (mid * mid > x) {
                    return end;
                } else {
                    return begin;
                }
            }
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                begin = mid;
            } else {
                end = mid;
            }

        }
        return begin;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        calculate(l1, l2, root);
        ListNode calculate = root.next;
        int add = 0;
        ListNode current = null;
        do {
            if (current == null) {
                current = calculate;
            } else {
                current = current.next;
            }
            int val = current.val + add;
            current.val = val % 10;
            add = val / 10;
            if (val / 10 >= 1 && current.next == null) {
                current.next = new ListNode(0);
            }
        } while (current.next != null);
        return calculate;
    }

    private static ListNode calculate(ListNode l1, ListNode l2, ListNode listNode) {
        if (l1 == null && l2 == null) {
            return listNode;
        }
        int v1 = l1 == null ? 0 : l1.val;
        int v2 = l2 == null ? 0 : l2.val;

        if (listNode == null) {
            listNode = new ListNode(v1 + v2);
        } else {
            listNode.next = new ListNode(v1 + v2);
        }

        return calculate(l1 == null ? null : l1.next, l2 == null ? null : l2.next, listNode.next != null ? listNode.next : listNode);
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return  0;
        }
        if(s.length() == 1){
            return 1;
        }
        int[] arr = null;


        int maxlength = 1;
        for (int i = 0; i < s.length(); i++) {
            arr = new int[130];
            arr[s.charAt(i)]++;
            for (int j = i + 1; j < s.length(); j++) {
                char c = s.charAt(j);
                arr[c]++;
                // int index = s.substring(i, j).indexOf(s.charAt(j));
                if (arr[c] <= 1 && j - i + 1> maxlength) {
                    maxlength = j - i + 1;
                } else if (arr[c] > 1) {
                    break;
                }
            }
        }
        return maxlength;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // System.out.println(solution.decodeAtIndex("leet2code3", 10));
        // System.out.println(solution.decodeAtIndex("ha22", 5));
        // System.out.println(solution.decodeAtIndex("a2345678999999999999999", 1));
        // System.out.println(solution.decodeAtIndex("a23", 6));
        // System.out.println(solution.decodeAtIndex("rew13h5xk8aewqewqr9s222v93y22ssssw2", 3113765));
        // System.out.println(solution.searchInsert(new int[] { 1, 2, 3, 4, 5, 10 }, 2));
        // System.out.println(solution.mySqrt(2147395599));
        // for (int i = 0; i < 30; i++) {
        // 	System.out.println(solution.mySqrt(i) + "  " + i);
        // }
        // ListNode listNode1 = new ListNode(2);
        // ListNode listNode2 = new ListNode(4);
        // ListNode listNode3 = new ListNode(3);
        // listNode1.next = listNode2;
        // listNode2.next = listNode3;
        //
        // ListNode node1 = new ListNode(5);
        // ListNode node2 = new ListNode(6);
        // ListNode node3 = new ListNode(4);
        // node1.next = node2;
        // node2.next = node3;
        //
        // addTwoNumbers(listNode1, node1);

        // ListNode listNode1 = new ListNode(1);
        // ListNode listNode2 = new ListNode(8);
        // listNode1.next = listNode2;
        //
        // addTwoNumbers(listNode1, new ListNode(0));
        int[] ints = solution.twoSum(new int[] { 2, 7, 11, 15 }, 9);
        System.out.println(ints == null ? "null" : ints.length);

        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        // System.out.println(lengthOfLongestSubstring("bbbbb"));
    }


	public int[] twoSum(int[] nums, int target) {
		int[] arr = new int[nums.length];
		for (int i = 0; i < nums.length; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] == nums[i]){
					return new int[]{j,i};
				}
			}
			arr[i] = target - nums[i];
		}
		return null;
	}

	/**
	 * 给定 nums = [2, 7, 11, 15], target = 9
	 *
	 * 因为 nums[0] + nums[1] = 2 + 7 = 9
	 * 所以返回 [0, 1]
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/two-sum
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 */


}